package dataStructure.string;

/**
 * 快速字符串匹配
 */
public class KMP {
    private static int[] getNext(String p) {
        int i, j;
        int[] next = new int[p.length() + 1];
        next[0] = -1;//next[0]放上-1
        i = 0;//指向字符串每个字符的指针
        j = -1;
        while (i < p.length()) {//没有到达结尾的话
            if (j == -1 || p.charAt(i) == p.charAt(j)) {//如果是第一个字符或遇到相同的字符
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        System.out.print("next:");
        for (i = 0; i < p.length(); i++) {//输出next[]值
            System.out.printf("%d ", next[i]);
        }
        System.out.println();
        return next;
    }

    private static int kmp(String t, String p, int[] next) {
        int i, j;
        i = j = 0;
        while (i < t.length() && j < p.length()) {
            if (j == -1 || t.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == p.length()) {
            return i - p.length();
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        String t = "gubojun is dfdd dfeign qwegjqw habha qwerwetg qwe ee fdfdf";
        String p = "habha";
        int index = kmp(t, p, getNext(p));
        System.out.println("index:" + index);
        System.out.println(t.substring(index));
    }
}
